<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 封装优先级队列
      function PriorityQueue() {
        // 创建一个内部类 用于保存元素和元素的优先级
        // priority 优先级 在本例子中是越小优先级越大
        function QueueElement(element, priority) {
          this.element = element
          this.priority = priority
        }

        // 封装属性(可以使用链表)
        this.items = []

        // 1.实现插入方法
        PriorityQueue.prototype.enqueue = function (element, priority) {
          // 1.1.创建QueueElement对象
          var queueElement = new QueueElement(element, priority)

          // 1.2.判断队列是否为空
          if (this.items.length === 0) {
            this.items.push(queueElement)
          } else {
            var added = false
            // 1.3.循环比较
            for (let i = 0; i < this.items.length; i++) {
              // 如果大于前一个的优先级
              if (queueElement.priority < this.items[i].priority) {
                // 插入
                this.items.splice(i, 0, queueElement)
                added = true
                break
              }
            }

            // 1.4.如果优先级还是最小，放到最后
            if (!added) {
              this.items.push(queueElement)
            }
          }
        }

        // 2.从队列中删除前端的元素
        PriorityQueue.prototype.dequeue = function () {
          return this.items.shift()
        }

        // 3.查看前端的元素
        PriorityQueue.prototype.font = function () {
          return this.items[0]
        }

        // 4.查看队列是否为空
        PriorityQueue.prototype.isEmpty = function () {
          return this.items.length == 0
        }

        // 5.查看队列中元素的个数
        PriorityQueue.prototype.size = function () {
          return this.items.length
        }

        // 6.toString方法
        PriorityQueue.prototype.toString = function () {
          var resultString = ''
          for (let i = 0; i < this.items.length; i++) {
            resultString +=
              this.items[i].element + '-' + this.items[i].priority + '\n'
          }
          return resultString
        }
      }

      // 测试代码
      var pq = new PriorityQueue()
      pq.enqueue('a', 2)
      pq.enqueue('b', 4)
      pq.enqueue('c', 1)
      pq.enqueue('d', 3)
      // 打印
      console.log(pq.toString())
      // c - 1
      // a - 2
      // d - 3
      // b - 4
    </script>
  </body>
</html>
